package com.zwy.alhorthms;

/**
 * 希尔排序
 * 原理跟插入排序相似，
 * 不同点在于当前的间隔n位进行插入
 * @author 天火
 * @className ShellSort
 */
public class ShellSort {


    public static void main(String[] args) {

        int[] arr = {8,14,2,6,7,19,1,11,4,3,10,16,18,17,20,15,13,12,5};
        sort(arr);
        print(arr);

    }

    static void swap(int[] arr,int j,int i){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    static void print(int[] arr){
        for(int value : arr){
            System.out.print(value + "    ");
        }
    }

    private static void sort(int[] arr){
        int knuth = 1;
        while (knuth < arr.length){
            knuth =knuth * 3 +1;
        }
        for(int gap = knuth; gap>0;gap = (gap-1)/3) {
            for (int j = gap; j < arr.length; j++) {
                for (int i = j; i > gap - 1; i -= gap) {
                    if (arr[i] < arr[(i - gap)]) {
                        swap(arr, i, i - gap);
                    }
                }
            }
        }



        }



}
